package com.sicheng.蓝桥.国赛准备.第十一届蓝桥杯JAVAB;

import java.util.HashSet;
import java.util.Set;

/**
 * @author zsc
 * @version 1.0
 * @date 2022/6/8 20:27
 */
public class D本质上升序列 {
    /**
     * 小蓝特别喜欢单调递增的事物。
     * 在一个字符串中，如果取出若干个字符，将这些字符按照在字符串中的顺序排列后是单调递增的，则成为这个字符串中的一个单调递增子序列。
     * 例如，在字符串 lanqiao 中，如果取出字符 n 和 q，则 nq 组成一个单调递增子序列。类似的单调递增子序列还有 lnq、i、ano 等等。
     * 小蓝发现，有些子序列虽然位置不同，但是字符序列是一样的，例如取第二个字符和最后一个字符可以取到 ao，取最后两个字符也可以取到 ao。小蓝认为他们并没有本质不同。
     * 对于一个字符串，小蓝想知道，本质不同的递增子序列有多少个？
     * 例如，对于字符串 lanqiao，本质不同的递增子序列有 21 个。它们分别是 l、a、n、q、i、o、ln、an、lq、aq、nq、ai、lo、ao、no、io、lnq、anq、lno、ano、aio。
     * 请问对于以下字符串（共 200 个小写英文字母，分四行显示）：（如果你把以下文字复制到文本文件中，请务必检查复制的内容是否与文档中的一致。在试题目录下有一个文件 inc.txt，内容与下面的文本相同）
     * tocyjkdzcieoiodfpbgcncsrjbhmugdnojjddhllnofawllbhf
     * iadgdcdjstemphmnjihecoapdjjrprrqnhgccevdarufmliqij
     * gihhfgdcmxvicfauachlifhafpdccfseflcdgjncadfclvfmad
     * vrnaaahahndsikzssoywakgnfjjaihtniptwoulxbaeqkqhfwl
     * <p>
     * 输出:
     * 3616159
     */

    public static void main(String[] args) {
        String s = "tocyjkdzcieoiodfpbgcncsrjbhmugdnojjddhllnofawllbhf" + "iadgdcdjstemphmnjihecoapdjjrprrqnhgccevdarufmliqij" + "gihhfgdcmxvicfauachlifhafpdccfseflcdgjncadfclvfmad" + "vrnaaahahndsikzssoywakgnfjjaihtniptwoulxbaeqkqhfwl";

        //dp[i] 表示 以s[i]结尾的递增子序列个数
        long[] dp = new long[s.length()];
        for (int i = 0; i < s.length(); i++) {
            dp[i] = 1;
            for (int j = 0; j < i; j++) {
                if (s.charAt(j) < s.charAt(i))
                    dp[i] += dp[j];
                else if (s.charAt(i) == s.charAt(j))
                    dp[i] -= dp[j];
            }
        }

        long res = 0;
        for (int i = 0; i < s.length(); i++) {
            res += dp[i];
        }
        System.out.println(res);

    }

    static StringBuilder path = new StringBuilder();
    static Set<String> res = new HashSet<>();

    //填空题 暴力搜索 有点儿过于暴力辽，如果是大题肯定超时
    static void dfs(String s, int start) {
        res.add(path.toString());
        if (path.length() > 0 && path.length() == 'z' - path.charAt(0) + 1) {
            return;
        }
        for (int i = start; i < s.length(); i++) {
            if (path.length() > 0 && path.charAt(path.length() - 1) == 'z')
                break;
            if (path.length() > 0 && s.charAt(i) <= path.charAt(path.length() - 1)) {
                continue;
            }
            path.append(s.charAt(i));
            dfs(s, i + 1);
            path.deleteCharAt(path.length() - 1);
        }
    }


}
